#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    //Boyer-Moore 投票算法
    int majorityElement(vector<int> &nums)
    {
        int candidate = -1;
        // votes
        int count = 0;
        for (int &num : nums)
        {
            if (count == 0)
            {
                candidate = num;
            }
            num == candidate ? count++ : count--;
        }
        count = 0;
        int length = nums.size();
        // get x
        for (int &num : nums)
        {
            if (num == candidate)
            {
                count++;
            }
        }
        return count * 2 > length ? candidate : -1;
    }
};
int main()
{
    Solution s;
    vector<int> nums = {1, 2, 5, 9, 5, 9, 5, 5, 5};
    cout << s.majorityElement(nums) << endl;
    system("pause");
    return 0;
}
